package hashTable

/*
方法一：hash+桶排序
时间复杂度：O(n)
空间复杂度：O(n)
*/

// hash+hash桶排序
func topKFrequent(nums []int, k int) []int {
	m := make(map[int]int)
	for _, v := range nums {
		m[v]++
	}

	bucket := make(map[int][]int)
	maxFrequent := 0
	// 记录数字出现频率到数字的映射
	for k, v := range m {
		bucket[v] = append(bucket[v], k)
		if maxFrequent < v {
			maxFrequent = v
		}
	}

	result := make([]int, 0)
	for i := maxFrequent; i > 0 && k > 0; i-- {
		if _, ok := bucket[i]; ok {
			result = append(result, bucket[i]...)
			k--
		}
	}
	return result
}

// hash+slice桶排序
func topKFrequent1(nums []int, k int) []int {
	m := make(map[int]int)
	for _, v := range nums {
		m[v]++
	}

	// 由于频率最大值可能为len(nums)，所以声明长度需要最少为 len(nums)+1
	bucket := make([][]int, len(nums)+1)
	for k, v := range m {
		bucket[v] = append(bucket[v], k)
	}

	result := make([]int, 0)
	for i := len(nums); i > 0 && len(result) < k; i-- {
		if len(bucket[i]) != 0 {
			continue
		}
		result = append(result, bucket[i]...)
	}
	return result
}
